/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 * 输入：m = 3, n = 7
输出：28
 */
// 动态规划-求到每一个格子的可走的次数 从 0 0 开始 到0 1 是一次 到1 0 是一次 到 1 1 就是两次，即当前格子左边走的次数加上边走的次数
var uniquePaths = function (m, n) {
  const f = new Array(m).fill(0).map(() => new Array(n).fill(0))
  // 边缘位置的走到的次数都是1
  for (let i = 0; i < m; i++) {
    f[i][0] = 1
  }
  for (let i = 0; i < n; i++) {
    f[0][i] = 1
  }
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      // 将当前格子的左边和上边的次数相加就是当前格子的次数
      f[i][j] = f[i][j - 1] + f[i - 1][j]
    }
  }
  return f[m - 1][n - 1]
}
console.log(uniquePaths(3, 7))
